package practice;

import java.util.Arrays;

/**
 * 挖金矿
 * 金矿含量：    200kg   300kg   350kg       400kg   500kg
 * 需要人数：    3       4       3           5       5
 *
 * 总人数10
 */
public class GoldMiner {
    public static void main(String[] args) {
        int n = 5;
        int w = 10;
        int[] k = {200, 300, 350, 400, 500};
        int[] p = {3, 4, 3, 5, 5};
        int s = mining3(k, p, n, w);
        System.out.println(s);
    }

    static int mining(int[] k,
                      int[] p,
                      int n,
                      int w) {
        if(n == 0 || w == 0)
            return 0;
        int x = mining(k, p, n - 1, w); // 不挖最后一个，在w个人里面选n-1个
        int y = w >= p[n - 1] ? // 当前人数够不够挖最后一个
                k[n - 1] + mining(k, p, n - 1, w - p[n - 1]) : // 挖最后一个
                x; // 不挖最后一个
        return Math.max(x, y);
    }

    static int mining2(int[] k, int[] p, int n, int w) {
        int[][] res = new int[w + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= w; i++) {
                if(j == 1) {
                    if(i < p[j - 1])
                        res[i][j] = 0;
                    else
                        res[i][j] = k[j - 1];
                } else {
                    int x = res[i][j - 1]; // 不挖最后一个
                    if (i < p[j - 1]) // 人数不够挖最后一个
                        res[i][j] = x;
                    else {
                        int y = k[j - 1] + res[i - p[j - 1]][j - 1]; // 挖最后一个
                        res[i][j] = Math.max(y, x);
                    }
                }
            }
        }
        return res[w][n];
    }

    static int mining3(int[] k, int[] p, int n, int w) {
        int[] res = new int[w + 1];
        for (int i = 0; i < n; i++) {
            for (int j = w; j >= p[i]; j--) {
                res[j] = Math.max(res[j], // 不挖当前这个
                        res[j - p[i]] + k[i]); // 挖当前这个
            }
        }
        System.out.println(Arrays.toString(res));
        return res[w];
    }
}
